package org.example.myleet.p934;

import java.util.LinkedList;
import java.util.Queue;

public class Solution {

    private static final int[][] DIRECTIONS = new int[][]{{-1, 0}, {0, 1}, {1, 0}, {0, -1}};

    public int shortestBridge(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        int[][] dp = new int[m][n];
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                dp[i][j] = Integer.MAX_VALUE;
            }
        }
        boolean[][] visited = new boolean[m][n];
        Queue<int[]> queueShore = new LinkedList<>();
        Queue<int[]> queue = new LinkedList<>();
        //BFS init find the tip of one island
        tag:
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (grid[i][j] == 1) {
                    dp[i][j] = 0;
                    queue.offer(new int[]{i, j});
                    visited[i][j] = true;
                    break tag;
                }
            }
        }
        //BFS one island
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; ++i) {
                int[] p = queue.poll();
                for (int k = 0; k < 4; ++k) {
                    int ni = p[0] + DIRECTIONS[k][0];
                    int nj = p[1] + DIRECTIONS[k][1];
                    if (0 <= ni && ni < m && 0 <= nj && nj < n) {
                        if (!visited[ni][nj]) {
                            if (grid[ni][nj] == 0) {
                                queueShore.offer(new int[]{ni, nj});
                                dp[ni][nj] = 1;
                            } else {
                                queue.offer(new int[]{ni, nj});
                                dp[ni][nj] = 0;
                            }
                            visited[ni][nj] = true;
                        }
                    }
                }
            }
        }
        //BFS DP touch the other island
        queue = queueShore;
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; ++i) {
                int[] p = queue.poll();
                for (int k = 0; k < 4; ++k) {
                    int ni = p[0] + DIRECTIONS[k][0];
                    int nj = p[1] + DIRECTIONS[k][1];
                    if (0 <= ni && ni < m && 0 <= nj && nj < n) {
                        if (!visited[ni][nj]) {
                            if (grid[ni][nj] == 1) {
                                return dp[p[0]][p[1]];
                            }
                            queue.offer(new int[]{ni, nj});
                            visited[ni][nj] = true;
                            dp[ni][nj] = Math.min(dp[ni][nj], dp[p[0]][p[1]] + 1);
                        }
                    }
                }
            }
        }
        return m + n;
    }
}
